The invention relates to the field of computer graphics processing. More specifically, the invention relates to a method and system for viewing details in representations of three-dimensional information while maintaining the context and, where occlusions of the detail is avoided.
Three-dimensional (xe2x80x9c3Dxe2x80x9d) representations of information present specific challenges not found in two-dimensional (xe2x80x9c2Dxe2x80x9d) representations, for example, in 3D representations certain elements may be occluded by the presence of other elements in the representation Traditional approaches to dealing with occlusion avoidance in 3D representations include techniques such as cutting planes, viewer navigation, filtering of information, and transparency. While these methods provide clearer visual access to elements of interest it removes much of the contextual information from a representation.
In 2D representations all information is restricted to a plane perpendicular to a view point. The addition of the third spatial variable (or z component) allows objects to be interposed or positioned between the viewpoint and other objects in a scene, thus partially or completely hiding them from view. The preservation of spatial relationships and presentation of relationships to the occluding objects is important in constructing a physically plausible scene or in other words the detail of the scene is maintained in the context in which it exists For example, in volumetric rendering of 3D data it is often the case that the near-continuous nature of the data makes occlusion of interior features of the data inevitable. This phenomenon is important in supporting perception of the scene as a 3D representation, but a user may very well wish to examine these hidden interior regions.
Solutions are available that provide visual access (i.e. clear lines of sight) to previously occluded elements. Several of these solutions are described by Cowperthwaite in Occlusion Resolution Operators for Three-Dimensional Derail-In-Context (Cowperthwaite, David J., Occlusion Resolution Operators for Three-Dimensional Detail-In-Context (Burnaby, British Columbia: Simon Fraser University, 2000)) which is incorporated herein by reference. Cutting planes may be used to remove information from a scene. Increasing transparency (or reducing the opacity) of objects allows more distant objects to be seen through those more proximal to the viewer. Navigation of the viewer, whether egocentric (moving the viewer within the data space) or exocentric (moving or re-orientation of the data space) may lead to a configuration where occlusion is resolved. Finally, information filtering may be used to reduce the density of data in a representation. These are all common methods of occlusion resolution and all operate by reducing the amount (or visibility) of contextual information in the final presentation. Similar methods such as panning zooming and filtering have also been traditionally applied to dealing with large or congested displays of information in two-dimensions. Thus, the removal of information from a presentation has been one approach to dealing with the large information spaces.
Another approach has been the development of xe2x80x9cdetail-in-contextxe2x80x9d presentation algorithms. The field of detail-in-context viewing is concerned with the generation of classes of information presentations where areas or items defined as focal regions or regions of interest (xe2x80x9cROIxe2x80x9d) are presented with an increased level of detail, without the removal of contextual information from the original presentation. For example, regions of greatest interest may be displayed at an enlarged size, providing more visual detail, while the scale of the surrounding context may be adjusted to provide the space for the magnification of the ROI.
In the detail-in-context discourse, differentiation is open made between the terms xe2x80x9crepresentationxe2x80x9d and xe2x80x9cpresentationxe2x80x9d. A xe2x80x9crepresentationxe2x80x9d is a formal system, or mapping, for specifying raw information or data that is stored in a computer or data processing system. For example, a digital map of a city is a representation of raw data including street names and the relative geographic location of streets and utilities. Such a representation may be displayed visually on computer screen or printed on paper. On the other hand, a presentation is a spatial organization of a given representation that is appropriate for the task at hand. Note also that the term xe2x80x9cvisualizationxe2x80x9d in computer graphics processing is often used to identify the process of applying computer graphics techniques to the problem of presenting information to users. That is, a xe2x80x9crepresentationxe2x80x9d is transformed into a xe2x80x9cpresentationxe2x80x9d through the process of visualization. Thus, a presentation of a representation organizes such things as the point of view and the relative emphasis of different parts or regions of the representation. For example, a digital map of a city may be presented with a work route magnified to reveal street names. Thus, detail-in-context presentations allow for magnification of a particular ROI in a representation while preserving visibility of the surrounding representation. In other words, in detail-in-context presentations focal regions are presented with an increased level of detail without the removal of contextual information from the original representation. In general, a detail-in-context presentation may be considered as a distorted view (or distortion) of a portion of the original representation where the distortion is the result of the application of a xe2x80x9clensxe2x80x9d like distortion function to the original representation. For reference, a detailed review of various detail-in-context presentation techniques may be found in Carpendale""s A Framework for Elastic Presentation Space (Carpendale, Marianne S. T., A Framework for Elastic Presentation Space (Burnaby, British Columbia: Simon Fraser University, 1999)) which is incorporated herein by reference.
The process of generating 2D detail-in-context presentations as described by Carpendale may be encompassed by the term Elastic Presentation Space (xe2x80x9cEPSxe2x80x9d). EPS includes techniques that allow for the adjustment of a visual presentation without interfering with the information content of the representation. The adjective xe2x80x9celasticxe2x80x9d is included in the term as it implies the capability of stretching and deformation and subsequent return to an original shape. Basically, in EPS graphics technology, a two-dimensional visual representation is placed onto a surface; this surface is placed in three-dimensional space; the surface, containing the representation, is viewed through perspective projection; and the surface is manipulated to effect the reorganization of image details. The presentation transformation is separated into two steps: surface manipulation or distortion and perspective projection. Extensions of classical 2D detail-in-context viewing algorithms to 3D by the addition of a z component do not adequately address the situation
To reiterate, a unique situation arises with detail-in-context viewing and 3D representations of information in that the possibility of the ROI being occluded exists. As discussed above, there are a number of methods which have been developed, independent of detail-in-context viewing, for dealing with situation of occlusion in 3D information representations. Each of these methods involves removing information from a display in some manner, which is contrary to the goals of detail-in-context viewing.
Several systems are known which provide techniques for occlusion avoidance in computer graphics systems. In U.S. Pat. No. 5,999,879 (Yano), a navigation apparatus for stereoscopically displayed road maps containing shape data for buildings, mountains, and similar landmarks is disclosed. With the disclosed apparatus, when a landmark object overlaps a section of road in stereoscopic view, the shape of the overlapping landmark may be changed so that the occluded section of road may be observed. The disclosed apparatus cannot provide detail-in-context presentations. In U.S. Pat. No. 5,689,628 (Robertson), a method and system are disclosed for maintaining a view of a selected display object while navigating in an n-dimensional, workspace. As such, the disclosed method and system exemplify, at most, a viewer navigation-like approach to occlusion avoidance. Thus, none of these systems disclose a method or system for occlusion avoidance in a maimer that is optimized for 3D information representations and detail-in-context viewing.
A need therefore exists for a method and system that will allow for effective occlusion avoidance and detail-in-context viewing of representations of three-dimensional data
The invention provides a method, system, computer program product, and integrated circuit product for occlusion avoidance and detail-in-context viewing of 3D information representations. The invention employs Occlusion Reducing Transformations to improve the visibility of objects-of-interest within 3D information representations by the displacement of occluding objects. The invention enables occlusion avoidance and hence the effective generation of 3D detail-in-context presentations. Occluding objects are generally displaced in directions away from the line of sight extending from a user""s viewpoint to the object-of-interest in the information representation.
According to one aspect of the invention, a method is provided for generating a detail-in-context presentation of a three-dimensional information representation. The method comprises the steps of selecting a object-of-interest in the information representation; selecting a viewpoint; selecting a source path from the viewpoint to the object-of-interest; and, displacing objects in the information representation away from the source path to locations within the information representation where the objects remain visible when viewed from the viewpoint yet do not occlude the object-of-interest when viewed from the viewpoint. With respect to the displacement of objects away from the source, the method further comprises the steps of, for each object, calculating a direction vector between the object and the nearest point on the source; calculating the magnitude of this direction vector; calculating a displacement vector having the same direction as the direction vector and having a magnitude based on the magnitude of the direction vector and given by a transformation function; and, displacing the object in the direction of the displacement vector a distance given by the magnitude of the displacement vector.
According to another aspect of the invention, a method is provided wherein the transformation function is such that objects located closest to the source are displaced the furthest and objects originally lying further away from the source are displaced in successively smaller increments such that a smooth transition is eventually made to objects that are located far enough away from the source as to require no displacement for occlusion avoidance purposes.
According to another aspect of the invention, a method is provided wherein the transformation function includes a detail-in-context distortion basis function
According to another aspect of the invention, a method is provided wherein the source is a line,
According to another aspect of the invention, a method is provided wherein the source is a plane.
According to another aspect of the invention, a method is provided wherein the plane is parallel to a plane containing a vector from the viewpoint to the object-of-interest.
According to another aspect of the invention, a method is provided wherein the plane is perpendicular to a plane containing a vector from the viewpoint to the object-of-interest.
According to another aspect of the invention, a method is provided wherein the plane is rotted with respect to a plane containing a vector from the viewpoint to the object-of-interest.
According to another aspect of the invention, a method is provided wherein the distribution of the transformation function across a plane perpendicular to a vector from the viewpoint to the object-of-interest is modified by a shaping function.
According to another aspect of the invention, a method is provided wherein the shaping function is operable to spatially constrain the operation of the transformation function.
According to another aspect of the invention, a method is provided wherein the shaping function is constant.
According to another aspect of the invention, a method is provided wherein the shaping function is Gaussian.
According to another aspect of the invention, a method is provided wherein the shaping function is linear.
According to another aspect of the invention, a method is provided wherein the shaping function is a user defined curve.
According to another aspect of the invention, a method is provided wherein the object-of-interest is the focus of the detail-in-context distortion basis function.
According to another aspect of the invention, a method is provided wherein the detail-in-context distortion basis function is linear.
According to another aspect of the invention, a method is provided wherein the detail-in-context distortion basis function is Gaussian.
According to another aspect of the invention, a method is provided wherein the detail-in-context distortion basis function is hemispherical.
According to another aspect of the invention, a method is provided wherein the detail-in-context distortion basis function is inverse hemispherical.
According to another aspect of the invention, a method is provided wherein the detail-in-context distortion basis function is trigonometric.
According to another aspect of the invention, a method is provided wherein the detail-in-context distortion basis function is user defined.
According to another aspect of the invention, a method is provided wherein the distribution of the transformation function along the source parallel to a vector from the viewpoint to the object-of-interest is defined by a distribution function.
According to another aspect of the invention, a method is provided wherein the distribution function is a z-axis distribution function.
According to another aspect of the invention, a method is provided wherein the distribution function is constant.
According to another aspect of the invention, a method is provided wherein the distribution function is linear.
According to another aspect of the invention, a method is provided wherein the linear distribution function continues through the three-dimensional data representation thereby isolating the object-of-interest.
According to another aspect of the invention, a method is provided wherein the distribution function is short linear.
According to another aspect of the invention, a method is provided wherein one end of the short linear distribution function terminates at the object-of-interest.
According to another aspect of the invention, a method is provided wherein the distribution function is truncated.
According to another aspect of the invention, a method is provided wherein the distribution function is truncated at the object-of-interest.
According to another aspect of the invention, a method is provided wherein the truncated distribution function includes a cap around the object-of-interest.
According to another aspect of the invention, a method is provided wherein the cap is hemispherical.
According to another aspect of the invention, a method is provided wherein the distribution function is a user defined curve.
According to another aspect of the invention, a method is provided wherein the magnitude of the displacement vector as given by the transformation function is defined by a distance metric.
According to another aspect of the invention, a method is provided wherein the distance metric is Euclidean.
According to another aspect of the invention, a method is provided wherein the distance metric is Lp as given by the equation dLp(x,y,z)=[((ABS(x)){circumflex over ( )}p+(ABS(y)){circumflex over ( )}p+(ABS(z)){circumflex over ( )}p]{circumflex over ( )}(1/p).
According to another aspect of the invention, a method is provided wherein the distance metric is super-quadratic.
According to another aspect of the invention, a method is provided wherein the distance metric is user defined.
According to anther aspect of the invention, a method is provided wherein the object-of-interest is a plurality of objects-of-interest.
According to another aspect of the invention, a data processing system is provided. This data processing system has stored therein data representing sequences of instructions which when executed cause the above-described method to be performed. The data processing system generally has an input device, a central processing unit, memory, and a display.
According to another aspect of the invention, a computer software product is provided. This computer software product contains sequences of instructions which when executed cause the above-described method to be performed.
According to another aspect of the invention, an integrated circuit product is provided. This integrated circuit product contains sequences of instructions which when executed cause the above-described method to be performed.
According to another aspect of the invention, the use of the above-described method to obtain an unobstructed view of a stored object in a display of the contents of a warehouse is provided. According to another aspect of the invention, the above-described use is provided wherein the stored object is an inventory item. According to another aspect of the invention, the above-described use is provided wherein the display is an electronic display. According to another aspect of the invention, the above-described use is provided wherein the display is a print-out. According to another aspect of the invention, the above-described use is provided wherein the warehouse is a shipping vessel.
According to another aspect of the invention, the use of the above-described method to obtain an unobstructed view of a person in a display of a group of people is provided. According to another aspect of the invention, the above-described use is provided wherein the display is an electronic display. According to another aspect of the invention, the above-described use is provided wherein the display is a print-out.
According to another aspect of the invention, the use of the above-described method to obtain an unobstructed view of a component within a three-dimensional drawing is provided. According to another aspect of the invention, the above-described use is provided wherein the drawing is a mechanical design drawing. According to another aspect of the invention, the above-described use is provided wherein the drawing is an engineering drawing. According to another aspect of the invention, the above-described use is provided wherein the drawing is a drawing of an automobile engine.
According to another aspect of the invention, the use of the above-described method to obtain an unobstructed view of a node in a three-dimensional network topology is provided. According to another aspect of the invention, the above-described use is provided wherein the network topology is a computer network.